#include <cstdlib>
#include <iostream>
#include <vector>
#include <fstream>
#include "affichage.hpp"
#include "../TP1/tp1.hpp"

using namespace std;

void pointrandom(int n, int poin[][2]);
void distances(int n, int m, int point[][2], int edge[][3]);
void tri(int m, int edge[][3]);
void kruskal(int n, int edge[][3], int arbre[][2]);

int main(){
  	int n;             //Le nombre de points.
  	cout << "Entrer le nombre de points: ";
  	cin >> n;
  	int m=n*(n-1)/2;   // Le nombre de paires de points.
  	int point[n][2];   // Les coordonnees des points dans le plan.
  	int edge[m][3];    // Les paires de points et le carre de leur longueur.
	int arbre[n-1][2]; // Les aretes de l’arbre de Kruskal.

	pointrandom(n, point);
	
	distances(n,m,point,edge);
	tri(m,edge);
	
//	kruskal(n, edge, arbre);
	
//	AffichageGraphique(n,point,arbre);

  	return 0;
}


void pointrandom(int n, int point[][2]){
	int alea1=0, alea2=0;
	srand(time(NULL));

	//initialisation du tableau point
	for (int i=0; i<n; i++){
		alea1=rand()%613;
		alea2=rand()%793;
		point[i][0]=alea1;
		point[i][1]=alea2;
	}

	//Affichage
	for (int i=0; i<n; i++){
		cout<<point[i][0]<<" ";
		cout<<point[i][1]<<endl;	
	}
	cout<<endl;
}


void distances(int n, int m, int point[][2], int edge[][3]){
	int k=0;	

	for (int i=0; i<n-1; i++){
		for (int j=i+1; j<n; j++){
			edge[k][0]=i;
			edge[k][1]=j;
			edge[k][2]= (point[i][0]-point[j][0])*(point[i][0]-point[j][0]) + (point[i][1]-point[j][1])*(point[i][1]-point[j][1]);
			k++;
		}
	}

	for (int i=0; i<m; i++){
		cout<<edge[i][0]<<" ";
		cout<<edge[i][1]<< " ";
		cout<<edge[i][2]<<" "<<endl;

	}
	cout<<endl;
}


void tri(int m, int edge[][3]){
	int flag1=0, flag2=0, flag0=0;

	//tri
	for (int i=0; i<m;i++){
		for (int j=i; j<m;j++){
			if (edge[i][2]>edge[j][2]){
				flag2=edge[i][2];
				edge[i][2]=edge[j][2];
				edge[j][2]=flag2;
				
				flag0=edge[i][0];
				edge[i][0]=edge[j][0];
				edge[j][0]=flag0;

				flag1=edge[i][1];
				edge[i][1]=edge[j][1];
				edge[j][1]=flag1;
			}
		}
	}

	//affichage
	for (int i=0; i<m; i++){
		cout<<edge[i][0]<<" ";
		cout<<edge[i][1]<< " ";
		cout<<edge[i][2]<<" "<<endl;
	}
	cout<<endl;
}


/*
* A COMPLETER
*/
void kruskal(int n ,int m, int edge[][3], int arbre[][2]){
	int comp[n];

	composantes(n,m,edge,comp);

	for (int i=0; i<n; i++){
		comp[i]=i;
	}

	for (int i=0; i<m; i++){
		if([][])
	}

}


